package Offer;

import org.junit.Test;

import java.util.*;

/**
 * @Description
 * @Author Firenut
 * @Date 2022-11-02 22:38
 */


/*
    题目:
        输入一个字符串，打印出该字符串中字符的所有排列。
        你可以以任意顺序返回这个字符串数组，但里面不能有重复元素
    思路:
        其实就是求全排列，组合问题
*/
public class T37_permutation {
    char[] ch;
    List<String> ans = new ArrayList<>();

    public String[] permutation2(String s){
        ch = s.toCharArray();
        dfs(0);
        return ans.toArray(new String[ans.size()]);
    }

    public void dfs(int x) {
        if (x == ch.length - 1) {
//            ans.add(ch.toString());
            ans.add(String.valueOf(ch));    // 添加排列方案 字符数组c的元素个数没变，只是一直在交换位置而已
            return;
        }

        Set<Character> set = new HashSet<>();

        //固定第x位的元素, 每一层递归，尝试将[i,c.length-1]的所有元素依次固定在x位置上
        for (int i = x; i < ch.length; i++) {
            if (set.contains(ch[i])) {// 重复，因此剪枝
                continue;
            }
            //先添加再交换
            set.add(ch[i]); //本层递归使用了ch[i]，本层递归后面的循环就不能再使用了(记录在set中)
            swap(i, x);     // 交换，将 c[i] 固定在第 x 位

            dfs(x + 1); // 开启固定第 x + 1 位字符
            swap(i, x);    // 恢复交换
        }
    }

    public void swap(int i, int j) {
        char temp = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;
    }

//    ====================================版本2==============================================
    @Test
    public void test() {
        permutation1("ab");
    }
    ArrayList<String> res = new ArrayList<>();


    /*
        执行效率太低了,如果在同一层递归选择的元素出现重复时，
        应该进行剪枝，不要再递归下去了,我在第一个版本的代码基础上
        修改了一下，虽然效率还是不行(递归的层数太多了，中间还
        是会有不必要的递归，因为for循环每层递归都从0开始，像k神那个
        是每一层递归x都会加1，for循环的i从x开始的，这样递归的层数会控制在 n！,效率因此提高了很多)
    * */
    public String[] permutation1(String s) {
        dfs1(s, new StringBuffer(), new boolean[s.length()]);
        return res.toArray(new String[s.length()]);
    }

    public void dfs1(String s, StringBuffer item, boolean[] flag) {
        if (item.length() == s.length()) {
//            res.add(item.toString());
            res.add(String.valueOf(item));
            return;
        }

        HashSet<Character> set = new HashSet<>(); //使用set是来固定每一位的数字不要出现重复
        for (int i = 0; i < s.length(); i++) {
            if (set.contains(s.charAt(i)) || flag[i]) {
                continue;
            }
            set.add(s.charAt(i));
            flag[i] = true;
            item.append(s.charAt(i));   //**
            dfs1(s, item, flag);

            flag[i] = false;
            if (item.length() != 0) {
                item.deleteCharAt(item.length() - 1);
            }
        }
    }
//    ==================================================================================


//    ==================================版本1================================================
    Set<String> set = new HashSet<>();  //存储结果集 (使用set达到去重的效果)
    /**
     * 如果序列中存在重复的字符 比如 a b b，那么就会出现重复排列的问题，所以需要考虑去重的问题
     * 此算法执行效率太低了,如果在同一层递归选择的元素出现重复时，此时应该进行剪枝，不要再递归下去了
     * @param s
     * @return
     */
    public String[] permutation(String s) {
        dfs(s, new StringBuffer(), new boolean[s.length()]);
        return set.toArray(new String[0]);//toArray方法：如果不带参数返回的是Object类型，带参数返回的是指定类型
    }

    /**
     * @param s
     * @param item 记录某一个组合
     * @param flag 标记数组元素是否可以被访问
     */
    public void dfs(String s, StringBuffer item, boolean[] flag) {
        if (item.length() == s.length()) {      //如果长度相同
            set.add(item.toString());
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            if (flag[i]) {
                continue;
            }

            item.append(s.charAt(i));
            flag[i] = true;
            dfs(s, item, flag);

            flag[i] = false;
            item.deleteCharAt(item.length() - 1);
        }
    }
//    ==================================================================================
}
